#!/usr/bin/python
#coding=utf8
#author linluxiang@gmail.com
#version=1.0.0 alpha
import thread
import lex
import sys
import StringIO
import symbols
from symbols import Node as Node

tokens=[]
now=0
tokensLength=0
string=[]
error=None
userIn=StringIO.StringIO()
userOut=StringIO.StringIO()
userOutflag=False

'''
This is the EBNF of cmm language.
program->(statement)*
statement->IfStatement
  | WhileStatement
  | AssignStatement
  | ReadStatement
  | WriteStatement
  | ComplexStatement
  | DefineStatement
DefineStatement->(<INT>|<REAL>)Identifier ["=" <INTEGER>|<REAL> ]";"
IfStatement-><IF> "(" Condition ")" Statement [<ELSE>Statement]
WhileStatement-><WHILE>"("Condition")"Statement
AssignStatement->(Identifier "=")+ Expression ";"
ReadStatement-><READ> "(" <IDENTIFY> ")" ";"
WriteStatement-><WRITE>"(" <EXPRESSION> ")" ";"
ComplexStatement->"{" Statement  (Statement() )*  "}"
ArrayStatement->"[" Expression() "]"
Condition->Expression <COMPARATION> Expression
Expression->Term() (<ADDOP> Term() )*
Term->Factor() (<MULOP> Factor() )*
Factor->[+|-]"(" Expression() ")" | Integer() | Real() | Identify()
Integer-><INTEGER>
Real-><REAL>
Identify-><IDENTIFY> ([ ArrayStatement ])*


语法分析是建立一棵语法树。递归下降分析法在分析的时候其实隐含的建立了一棵语法树。
'''

parse=Node()
#--------以下实现的是打印函数-------------
dev=0
def printTree(node):
    global dev
    s=' '*dev*2
    #print node
    if isinstance(node,Node):
        print>>userOut, '%s%s'%(s,node.value[0])
        if len(node.value)>1:
            for i in node.value[1:]:
                dev+=1
                printTree(i)
                dev-=1
    else:
        print>>userOut, '%s%s'%(s,node[1])
        
#---------以下实现的是具体的函数--------
'''
Error 处理函数
'''
def Error(str):
    global error,useroutflag
    print>>userOut,str
    #sys.exit(1)
    userOutflag=True
    thread.exit()
    #sys.exit(1)
'''
以下是match函数，用来判断当前Token串中的符号和参数是否一致。如果不一致就报错。如果一致就把now加1,就是把token串往后移
动一个。
'''
def match(tokenExpected):
    global now,tokens,tokensLength
    if now<len(tokens):
        tokenNow=tokens[now]
        if tokenNow[0] in('Identify','Integer','Real'):
            if (tokenNow[0]==tokenExpected[0]):
                now+=1
                return True
            else:
                Error("Synatax Error!In match get '%s' while expecting '%s',in line %s."%(tokenNow[1],tokenExpected[1],tokenNow[2]))
        else:
            tokenModel=(tokenNow[0],tokenNow[1],)
            if (tokenModel == tokenExpected) or (tokenModel in tokenExpected):
                now+=1
                return True
            else:
                Error("Synatax Error!In match get '%s' while expecting '%s',in line %s."%(tokenNow[1],tokenExpected[1],tokenNow[2]))
    else:
        Error("Missing '%s'."%(tokenExpected[1]))
'''
以下是Program开始。
以下所有的函数具有相似的结构。
根据EBNF，遇到非终结符就转移到与非终结符同名的函数中。
遇到终结符就match当前获得的Token和预期获得的Token是否一致。就是match函数的作用。
如果不一致。说明2点，1，有可能程序写错了。2,说明Token串不对，源代码有问题。报Error。
'''
def Program():
    global tokens,now,tokensLength
    node=Node()
    node.add('Program')
    while (now<tokensLength):
        node.add(Statement())
    return node 
'''
以下是statement开始
'''
def Statement():
    global tokens
    t=Node()
    node=Node()
    node.add('Statement')
    token=tokens[now]
    if token[0]=='Identify':
        t=AssignStatement()
    elif token[1]=='if':
        t=IfStatement()
    elif token[1]=='while':
        t=WhileStatement()
    elif token[1]=='read':
        t=ReadStatement()
    elif token[1]=='write':
        t=WriteStatement()
    elif token[1]=='{':
        t=ComplexStatement()
    elif token[1] in ('int','real'):
        t=DefineStatement()
    else:
        Error('Error in Statement,while token=%s'%(token,))
    node.add(t)
    return node
'''
以下是AssignStatement开始，表示赋值句
'''
def AssignStatement():
    global tokens,tokensLength
    node=Node()
    node.add('AssignStatement')
    node.add(Identify())
    match(symbols.AssignOp)
    node.add(symbols.AssignOp)
    #tokenNow=tokens[now]
    #while tokenNow[0] == 'Identify':
    #    node.add(Identify());
    #    node.add(Op(symbols.AssignOp))
    #    tokenNow=tokens[now];
    node.add(Expression())
    match(symbols.StatementEnd)
    node.add(tokens[now-1])
    return node
'''
以下是IfStatement开始
'''
def IfStatement():
    global tokens
    node=Node()
    node.add('IfStatement')
    match(symbols.IfKeyword)
    node.add(symbols.IfKeyword)
    match(('Separation','(',))
    node.add(('Separation','(',))
    node.add(Condition())
    match(('Separation',')',))
    node.add(('Separation',')',))
    node.add(Statement())
    if now<tokensLength:
        token=tokens[now]
        if token[1]=='else':
            match(symbols.ElseKeyword)
            node.add(symbols.ElseKeyword)
            node.add(Statement())
    return node

'''
以下是WhileStatement开始
'''
def WhileStatement():
    global tokens
    node=Node()
    node.add('WhileStatement')
    match(symbols.WhileKeyword)
    node.add(symbols.WhileKeyword)
    match(('Separation','(',))
    node.add(('Separation','(',))
    node.add(Condition())
    match(('Separation',')',))
    node.add(('Separation',')',))
    node.add(Statement())
    return node
'''
以下是ReadStatement的开始
'''
def ReadStatement():
    global tokens
    node=Node()
    node.add('ReadStatement')
    match(symbols.ReadKeyword)
    node.add(symbols.ReadKeyword)
    token=tokens[now]
    match(('Separation','(',))
    node.add(('Separation','(',))
    node.add(Identify())
    match(('Separation',')',))
    node.add(('Separation',')',))
    match(symbols.StatementEnd)
    node.add(symbols.StatementEnd)
    return node
'''
以下是WriteStatement的开始
'''
def WriteStatement():
    global tokens
    node=Node()
    node.add('WriteStatement')
    match(symbols.WriteKeyword)
    node.add(symbols.WriteKeyword)
    match(('Separation','(',))
    node.add(('Separation','(',))
    node.add(Expression())
    match(('Separation',')',))
    node.add(('Separation',')',))
    match(symbols.StatementEnd)
    node.add(symbols.StatementEnd)
    return node
'''
以下是ComplexStatement的开始，主要作用是复杂的Statement，就是大括号内的。
ComplexStatement->"{" Statement  (";" Statement() )*  "}"
'''
def ComplexStatement():
    global tokens
    node=Node()
    node.add('ComplexStatement')
    match(('Separation','{',))
    node.add(('Separation','{',))
    node.add(Statement())
    token=tokens[now]
    while token[1]!='}':
        node.add(Statement())
        token=tokens[now]
    match(('Separation','}'))
    node.add(('Separation','}',))
    return node
'''
以下是DefineStatement的开始，用于声明语句。
'''
def DefineStatement():
    global tokens
    node=Node()
    node.add('DefineStatement')
    match(symbols.DefineWord)
    node.add(tokens[now-1])
    node.add(Identify())
    token=tokens[now]
    if token[1]=='=':
        node.add(Op(symbols.AssignOp))
        node.add(Expression())
    match(symbols.StatementEnd)
    node.add(tokens[now-1])
    return node

'''
以下是ArrayStatement开始
'''
def ArrayStatement():
    global tokens
    node=Node()
    node.add('ArrayStatement')
    match(symbols.ArrayStartOp)
    node.add(symbols.ArrayStartOp)
    node.add(Expression())
    match(symbols.ArrayEndOp)
    node.add(symbols.ArrayEndOp)
    return node
'''
以下是Op开始
'''
def Op(op):
    global tokens
    node=Node()
    node.add('Operator')
    match(op)
    node.add(tokens[now-1])
    return node
'''
以下是Condition开始
'''
def Condition():
    global tokens
    node=Node()
    node.add('Condition')
    node.add(Expression())
    node.add(Op(symbols.ComparationOp))
    node.add(Expression())
    return node
'''
以下是Expression开始
'''
def Expression():
    global tokens
    node=Node()
    node.add('Expression')
    token=tokens[now]
    node.add(Term())
    token=tokens[now]
    while token[1]=='+' or token[1]=='-':
        node.add(Op(symbols.AddOp))
        node.add(Term())
        token=tokens[now]
    return node
'''
以下是Term开始
'''
def Term():
    global tokens
    node=Node()
    node.add('Term')
    node.add(Factor())
    if now<tokensLength:
        token=tokens[now]
        while token[1]=='*' or token[1]=='/':
            node.add(Op(symbols.MulOp))
            node.add(Factor())
            token=tokens[now]
        return node
    else:
        Error('Missing part in Statement.')
'''
以下是Factor开始
'''
def Factor():
    global tokens
    node=Node()
    node.add('Factor')
    token=tokens[now]
    if token[1] in ('+','-'):
        node.add(Op(symbols.AddOp))
        token=tokens[now]
    if token[1]=='(':
        match(('Separation','(',))
        node.add(tokens[now-1])
        node.add(Expression())
        match(('Separation',')',))
        node.add(tokens[now-1])
    elif token[0]=='Integer':
        node.add(Integer())
    elif token[0]=='Real':
        node.add(Real())
    elif token[0]=='Identify':
        node.add(Identify())
    else:
        Error('Wrong Expression!')
    return node
               
'''
以下是Identify开始
'''        
def Identify():
    global tokens,now
    node=Node()
    node.add('Identify')
    match(symbols.Identify)
    node.add(tokens[now-1])
    token=tokens[now]
    while token[1]=='[':
        node.add(ArrayStatement())
        token=tokens[now]
    return node
'''
以下是Integer开始
'''
def Integer():
    global tokens
    node=Node()
    node.add('Integer')
    match(symbols.Integer)
    node.add(tokens[now-1])
    return node
def Real():
    global tokens
    node=Node()
    node.add('Real')
    match(symbols.Real)
    node.add(tokens[now-1])
    return node
'''
以下是main函数
'''
def main(argv=None):
    global tokens,tokensLength,parse
    option='y'
    while option=='y':

        if argv==None:
            filename=raw_input('Please input the filename:')
            
        else:
            filename=args
        file=open(filename,'rU')
        lines=file.readlines()
        file.close()
        parse=getTree(lines)
        if isinstance(parse,Node):
            printTree(parse)
            for i in string:
                print>>userOut,i,
        else:
            print>>userOut,parse

        option=''

        while option!='y' and option!='n':
            option =raw_input('Please input "y" to analyze another file,"n" to quit the program:')

def getTree(lines):
    global tokens,tokensLength,error,now,userIn,userOut,userOutflag
    tokens=[]
    now=0
    tokensLength=0
    error=None
    userOutflag=False
    if __name__=='__main__':
        userIn=sys.stdin
        userOut=sys.stdout
    lex.userIn=userIn
    lex.userOut=userOut
    tokens=lex.getTokenList(lines)
    if isinstance(tokens,list):
        tokensLength=len(tokens)
        parse=Program()
        #tree=parse
        userOutflag=True
        return parse


if __name__=='__main__':
    length=len(sys.argv)
    if length>1:
        main(sys.argv[1])
    else:main()

